class Solution {
    public double myPow(double x, int n) {
        //如果n小于0，则结果等于当指数为-n时结果的倒数
        return n >= 0 ? pow(x, n) : 1.0 / pow(x, -n);
    }
    private double pow(double x, long n) {
        if(n == 0) return 1.0;
        double tmp = pow(x, n / 2);
        //如果n是偶数，x ^ n 等于 x ^ n/2 * x ^ n/2 ;
        //如果n是奇数，x x ^ n 等于 x ^ n/2 * x ^ n/2 * n
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
    }
    public int minPathSum(int[][] grid) {
        // 1. 创建dp表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值

        int m = grid.length+1;
        int n = grid[0].length+1;
        int[][] dp = new int[m][n];

        for(int row = 0; row < m; row++) {
            dp[row][0] = Integer.MAX_VALUE;
        }
        for(int col = 2; col < n; col++) {
            dp[0][col] = Integer.MAX_VALUE;
        }

        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];
            }
        }

        return dp[m-1][n-1];
    }
}
